ChristmasError-Blog

C++ GeneralizedTable 广义表实现

C++ 数据结构 广义表
字数统计: 556阅读时长: 3 min
2018/12/20 Share

结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
////Generalized_node.h
#include<iostream>
#include<assert.h>
enum Nodetype{
	HEAD,
	VALUE,
	SUB,
};
struct Generalized_node {
	Nodetype _type;
	Generalized_node *_next;

	union {
		char _value;
		Generalized_node *_sub;
	};
	Generalized_node(Nodetype type, const char value=' ') :_type(type),_next(NULL){
		if (type==VALUE||type==HEAD) {
			_value = value;
		}
		else if (_type == SUB) {
			_sub = NULL;
		}
		else 
			assert(false);
	}
};

广义表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

//Generalized_list.h
#include"Generalized_node.h"
/*
enum Nodetype{
HEAD,
VALUE,
SUB,
};
*/
class Generalized_list {
private:
	typedef Generalized_node Node;
	Node* _head;

	Node* createlist(const char *&str);
	//判断传入数据中字符是否有效
	inline bool useful(const char s) {
		if ((s >= '0'&&s <= '9')
			|| (s >= 'a'&&s <= 'z')
			|| (s >= 'A'&&s <= 'Z')) {
			return true;
		}
		return false;
	}
	void _print(Node * node);
	void _destory(Node *_head);
	size_t _depth(Node* _head);
public:
	Generalized_list():_head(NULL) {};
	Generalized_list(const char* str) {
		_head = createlist(str);
	};
	~Generalized_list()
	{
		_destory(_head);
	}
	//递归打印广义表
	void print() {
		_print(_head);
	}
	size_t depth()
	{
		size_t dep=_depth(_head);
		return dep;
	}

};
//构造函数
Generalized_node* Generalized_list::createlist(const char *&str) {
	assert(*str == '(');
	Node* head = new Node(HEAD, *str);
	Node* prev = head;
	head->_type = HEAD;
	++str;
	while (*str)
	{
		if (useful(*str))
		{
			Node* node = new Node(VALUE, *str);
			prev->_next = node;
			prev = prev->_next;
			++str;
		}
		else if (*str == '(') {
			Node *node = new Node(SUB, *str);
			prev->_next = node;
			prev = prev->_next;
			node->_sub = createlist(str);
			++str;
		}
		else if (*str == ')') {
			prev->_next = NULL;
			str++;
			return head;
		}
		else
		{
			++str;
		}
	}
	return head;
}
//打印广义表
void Generalized_list::_print(Node * node) {
	assert(node);
	Node *cur = node;
	while (cur) {
		if (cur->_type == VALUE)
		{
			std::cout << cur->_value;
			if (cur->_next != NULL)
				std::cout << ',';
			cur = cur->_next;
		}
		else if (cur->_type == SUB)
		{
			_print(cur->_sub);
			if (cur->_next != NULL)
				std::cout << ',';
			cur = cur->_next;
		}
		else
		{
			std::cout << '(';
			cur = cur->_next;
		}
	}
	std::cout << ')';
}
//销毁广义表
void Generalized_list::_destory(Node *_head)
{
	Node* cur = _head;
	while (cur)
	{
		Node* del = cur;
		if (cur->_type == SUB)
		{
			_destory(cur->_sub);
		}
		cur = cur->_next;
		delete[] del;
	}
}
//广义表深度
size_t Generalized_list::_depth(Node* _head)
{
	Node* cur = _head;
	size_t maxdep = 1;
	while (cur)
	{
		size_t dep = 1;
		if (cur->_type == SUB)
		{
			dep+=_depth(cur->_sub);
			if (dep > maxdep)
				maxdep = dep;
		}
		cur = cur->_next;
	}
	return maxdep;
}

测试运行结果

1
2
3
4
5
6
7
8
9
10
11
12
//test.cpp
#include"Generalized_list.h"
using namespace std;
int main() {
	const char *test = "(a,b,(c,d),(e,(f),h))";
	Generalized_list gl1(test);
	gl1.print();
	cout << "\n该表深度为" << gl1.depth();
	cout << endl;
	system("pause");
	return 0;
}

在这里插入图片描述

代码：
https://github.com/ChristmasError/Data_Structure/tree/master/%E5%B9%BF%E4%B9%89%E8%A1%A8%20Generalized%20table

CATALOG
  1. 1. 结点
  2. 2. 广义表
  3. 3. 测试运行结果
Total : 16
2018
C++ 数据结构 BST Lambda表达式 Lambda函数 C++ 数据结构 广义表 指针，const C++ 红黑树 数据结构 RBTree hash_map 哈希表 这是建立个人Blog来的第一篇测试博客 RAII 智能指针 很基础的Markdown语法及其效果演示 《深入了解计算机系统》 leetcode刷题笔记 STL学习笔记